package 二分查找;
/*n-1的递增数组，所有数字唯一，查找缺失的一个数字
* 用1.哈希。2.直接遍历3.位运算 ：异或 4.高斯求和
* 我用二分查找，根据数组的索引与数组是否一致来划分两个板块
* 左板块索引与值完全一致，右板块索引与值不一致，缺失的数在右版块中*/
public class 缺失的数字0到n中 {
    public int missingNumber(int [] nums){
        //二分解法
        int left = 0,right = nums.length-1;
        while (left < right){
            int mid = left+(right-left)/2;

            if(nums[mid] == mid){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        // 处理细节
        return nums[left] == left ? left+1 : left;
    }
}
